Image editing is the process of altering images by manipulating, enhancing or transforming their contents. Techniques for synthesizing both texture and complex image structures that qualitatively resemble those appearing in source images form the basis for a variety of interactive image editing tools, such as image retargeting, image completion and image reshuffling. For example, image retargeting allows images to be resized to a new aspect ratio, where the computer automatically produces a good likeness of the contents of the original image but with new dimensions. In another example, image completion allows unwanted portions of an image to be erased, and the computer automatically fills the erased region with synthesized content that plausibly matches the remainder of the image. In yet another example, image reshuffling makes it possible to grab portions of the image and move them around, and the computer automatically synthesizes the remainder of the image so as to resemble the original while respecting the moved regions. These tools can use patch-based sampling techniques for identifying patches of correspondence within images. However, some of these sampling techniques are computationally complex, and therefore can consume large amounts of both time and processing resources.